package com.data.construct.binaryTree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 层序遍历二叉树
 * BFS(Breadth-First Search)，即广度优先搜索
 *
 * @author sunhl
 * @Description:
 * @Date: created in 2024/11/11 0011 10:32
 * @Modified By:
 */
public class BFSBinaryTree {

    /**
     * 简单写法
     * 每次把队头元素拿出来，然后把它的左右子节点加入队列，就完事了。
     * 缺点是，无法知道当前节点在第几层。
     *
     * 也因此这种写法用的不多
     *
     * @param root
     */
    void levelOrderTraverse1(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode cur = q.poll();
            // 访问 cur 节点
            System.out.println(cur.val);

            // 把 cur 的左右子节点加入队列
            if (cur.left != null) {
                q.offer(cur.left);
            }
            if (cur.right != null) {
                q.offer(cur.right);
            }
        }
    }

    /**
     * 最常用写法
     * 对上面方法稍作改造, 主要是记录了遍历节点所在的层数
     * 可以解决诸如二叉树最小深度这样的问题，是我们最常用的层序遍历写法。
     *
     * @param root
     */
    void levelOrderTraverse2(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        // 记录当前遍历到的层数（根节点视为第 1 层）
        int depth = 1;

        while (!q.isEmpty()) {
            // 队列的长度 sz 一定要在循环开始前保存下来，因为在循环过程中队列的长度是会变化的，不能直接用 q.size() 作为循环条件。
            int sz = q.size();

            // 这个变量 i 记录的是节点 cur 是当前层的第几个，大部分算法题中都不会用到这个变量
            // 也可以用 while (sz-- > 0) 来代替
            for (int i = 0; i < sz; i++) {
                // 弹出队首元素, 这一步取出了当前遍历的元素, 也保证队列的按层排序
                TreeNode cur = q.poll();
                // 访问 cur 节点，同时知道它所在的层数
                System.out.println("depth = " + depth + ", val = " + cur.val);

                // 把 cur 的左右子节点加入队列
                if (cur.left != null) {
                    q.offer(cur.left);
                }
                if (cur.right != null) {
                    q.offer(cur.right);
                }
            }

            depth++;
        }
    }

    /**
     * 写法三
     * 让每一个节点在遍历过程中, 可以维护自己的路径权重和
     * 每个节点都有了自己的 depth 变量，是最灵活的，可以满足所有 BFS 算法的需求
     * 节点需要被State包一层, 再往队列中放
     * 这种边带有权重的场景属于图结构算法，在之后的BFS 算法习题集 和 dijkstra 算法 中，才会用到这种写法。
     *
     * @param root
     */
    void levelOrderTraverse3(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<State> q = new LinkedList<>();
        // 根节点的路径权重和是 1
        q.offer(new State(root, 1));

        while (!q.isEmpty()) {
            State cur = q.poll();
            // 访问 cur 节点，同时知道它的路径权重和
            System.out.println("depth = " + cur.depth + ", val = " + cur.node.val);

            // 把 cur 的左右子节点加入队列
            if (cur.node.left != null) {
                q.offer(new State(cur.node.left, cur.depth + 1));
            }
            if (cur.node.right != null) {
                q.offer(new State(cur.node.right, cur.depth + 1));
            }
        }
    }
}
